package com.lims.algorithm.algset.tree;

import java.util.Arrays;
import java.util.Stack;
import java.util.stream.Stream;

/**
 * <功能简述>遍历二叉树
 *
 * @author: lims
 * @create: 2019-04-19 10:26
 */
public class BinaryTree {
    static class BinaryTreeNode {
        public int data;
        public BinaryTreeNode left;
        public BinaryTreeNode right;

        public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {
            super();
            this.data = data;
            this.left = left;
            this.right = right;
        }

        public BinaryTreeNode(int data) {
            this.data = data;
        }
    }

    /**
     * -------------------1
     * -----------------/  \
     * ----------------2    3
     * ----------------/ \  / \
     * ---------------4  5  6  7
     * ---------------/  \
     * --------------8    9
     * -------------------\
     * -------------------10
     */

    //先序遍历 递归
    public static void preOrderRecur(BinaryTreeNode root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrderRecur(root.left);
            preOrderRecur(root.right);
        }
    }

    //中序遍历 递归
    public static void inOrderRecur(BinaryTreeNode root) {
        if (root != null) {
            inOrderRecur(root.left);
            System.out.print(root.data + " ");
            inOrderRecur(root.right);
        }
    }

    //后中序遍历 递归
    public static void postOrderRecur(BinaryTreeNode root) {
        if (root != null) {
            postOrderRecur(root.left);
            postOrderRecur(root.right);
            System.out.print(root.data + " ");
        }
    }

    /**
     * 非递归
     */

    //先序遍历 非递归
    public static void preOrder(BinaryTreeNode root) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        while (true) {
            while (root != null) {
                System.out.print(root.data + " ");
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty()) {
                break;
            }
            root = stack.pop().right;
        }
    }

    //中序遍历 非递归
    public static void inOrder(BinaryTreeNode root) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty()) {
                break;
            }
            System.out.print(stack.lastElement().data + " ");
            root = stack.pop().right;
        }
    }


    /**
     * 思路：
     * 1.向左循环压栈，遇到空时判断
     * 2.判断栈顶的右结点状态。根据为空或不为空状态，将root指针指向栈顶或者右结点
     * 3.root指向右结点时，再判断栈顶对应右结点状态，判断右结点状态和root指针关系，确定继续压栈操作or作为最右链路依次向上弹出
     * <p>
     * PS:最右链路向上弹出到底后，为保证已经出栈结点不重复压栈，root重置为null（只判断栈顶结点）
     * <p>
     * 后序遍历 非递归 单栈法
     *
     * @param root
     */
    public static void postOrderSingleStack(BinaryTreeNode root) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        while (true) {
            if (null != root) {
                stack.push(root);
                root = root.left;
            } else {
                if (stack.isEmpty()) {
                    break;
                }
                if (stack.peek().right != null) {
                    root = stack.peek().right;
                } else {
                    root = stack.pop();
                    System.out.print(root.data + " ");
                    while (stack.peek().right == root) {
                        root = stack.pop();
                        System.out.print(root.data + " ");
                        if (stack.isEmpty()) {
                            break;
                        }
                    }
                    root = null;
                }
            }
        }
    }

    //后序遍历 非递归（单栈法2）
    public static void postOrder(BinaryTreeNode root) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        while (true) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                if (stack.isEmpty()) {
                    return;
                }
                if (stack.lastElement().right == null) {
                    root = stack.pop();
                    System.out.print(root.data + " ");
                    if (stack.isEmpty()) {
                        return;
                    }
                    while (root == stack.lastElement().right) {
                        root = stack.pop();
                        System.out.print(root.data + " ");
                        if (stack.isEmpty()) {
                            break;
                        }
                    }
                }
                if (!stack.isEmpty()) {
                    root = stack.lastElement().right;
                } else {
                    root = null;
                }
            }
        }
    }

    //后序遍历 非递归 双栈法
    public static void postOrderTwoStack(BinaryTreeNode root) {
        Stack<BinaryTreeNode> stack1 = new Stack<>();
        Stack<BinaryTreeNode> stack2 = new Stack<>();
        if (root != null) {
            stack1.push(root);
            while (!stack1.isEmpty()) {
                root = stack1.pop();
                stack2.push(root);
                if (root.left != null) {
                    stack1.push(root.left);
                }
                if (root.right != null) {
                    stack1.push(root.right);
                }
            }
            while (!stack2.isEmpty()) {
                System.out.print(stack2.pop().data + " ");
            }
        }
    }

    /**
     * 构建二叉树
     *
     * @param pre
     * @param in
     * @return
     */
    public static BinaryTreeNode reConstruct(int[] pre, int[] in) {
        if (pre == null || in == null) {
            return null;
        }
        // 根结点
        int rootData = pre[0];
        BinaryTreeNode root = new BinaryTreeNode(rootData, null, null);
        if (pre.length == 1 && in.length == 1) {
            if (pre[0] == in[0]) {
                return root;
            } else {
                System.out.println("输入有错!");
            }
        }

        // 根结点在in中的索引
        int rootIndex = -1;
        for (int i = 0; i < in.length; ++i) {
            if (rootData == in[i]) {
                rootIndex = i;
                break;
            }
        }

        // 有左子树
        if (rootIndex > 0) {
            root.left = reConstruct(
                    Arrays.copyOfRange(pre, 1, rootIndex + 1),
                    Arrays.copyOfRange(in, 0, rootIndex)
            );
        }
        // 有右子树
        if (rootIndex < in.length - 1) {
            root.right = reConstruct(
                    Arrays.copyOfRange(pre, rootIndex + 1, pre.length),
                    Arrays.copyOfRange(in, rootIndex + 1, in.length)
            );
        }
        return root;
    }


    public static void main(String[] args) {
        /**
         ---------1
         --------/  \
         -------2    3
         ------/ \  / \
         -----4  5  6  7
         -------/ \
         ------8  9
         ----------\
         ----------10
         */
        BinaryTreeNode node10 = new BinaryTreeNode(10, null, null);
        BinaryTreeNode node8 = new BinaryTreeNode(8, null, null);
        BinaryTreeNode node9 = new BinaryTreeNode(9, null, node10);
        BinaryTreeNode node4 = new BinaryTreeNode(4, null, null);
        BinaryTreeNode node5 = new BinaryTreeNode(5, node8, node9);
        BinaryTreeNode node6 = new BinaryTreeNode(6, null, null);
        BinaryTreeNode node7 = new BinaryTreeNode(7, null, null);
        BinaryTreeNode node2 = new BinaryTreeNode(2, node4, node5);
        BinaryTreeNode node3 = new BinaryTreeNode(3, node6, node7);
        BinaryTreeNode node1 = new BinaryTreeNode(1, node2, node3);

        System.out.println("====先序遍历 递归====");
        preOrderRecur(node1);
        System.out.println(" ");

        System.out.println("====中序遍历 递归====");
        inOrderRecur(node1);
        System.out.println(" ");

        System.out.println("====后序遍历 递归====");
        postOrderRecur(node1);
        System.out.println(" ");

        System.out.println("====先序遍历 非递归====");
        preOrder(node1);
        System.out.println(" ");

        System.out.println("====中序遍历 非递归====");
        inOrder(node1);
        System.out.println(" ");

        System.out.println("====后序遍历 非递归====");
        postOrder(node1);
        System.out.println(" ");

        System.out.println("====后序遍历 非递归 双栈法====");
        postOrderTwoStack(node1);
        System.out.println(" ");

        System.out.println("====后序遍历 非递归 单栈法====");
        postOrderSingleStack(node1);
        System.out.println(" ");


        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        BinaryTreeNode root = reConstruct(pre, in);
        System.out.println("构建二叉树");
        System.out.println("====先序遍历 递归====");
        preOrderRecur(root);
        System.out.println(" ");

        System.out.println("====中序遍历 递归====");
        inOrderRecur(root);
        System.out.println(" ");

        System.out.println("====后序遍历 递归====");
        postOrderRecur(root);
        System.out.println(" ");
    }
}
